//给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。 
//
// 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 
//
// 此外，你可以假设该网格的四条边均被水包围。 
//
// 
//
// 示例 1： 
//
// 
//输入：grid = [
//  ["1","1","1","1","0"],
//  ["1","1","0","1","0"],
//  ["1","1","0","0","0"],
//  ["0","0","0","0","0"]
//]
//输出：1
// 
//
// 示例 2： 
//
// 
//输入：grid = [
//  ["1","1","0","0","0"],
//  ["1","1","0","0","0"],
//  ["0","0","1","0","0"],
//  ["0","0","0","1","1"]
//]
//输出：3
// 
//
// 
//
// 提示： 
//
// 
// m == grid.length 
// n == grid[i].length 
// 1 <= m, n <= 300 
// grid[i][j] 的值为 '0' 或 '1' 
// 
// Related Topics 深度优先搜索 广度优先搜索 并查集 数组 矩阵 
// 👍 1213 👎 0


package service.week03.leetcode.editor.cn;







//import java.util.ArrayDeque;
//import java.util.Queue;
//import javafx.util.Pair;

//Java：岛屿数量
public class P200NumberOfIslands {
    public static void main(String[] args) {
        Solution solution = new P200NumberOfIslands().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 地图bfs 模板
         *
         * @param grid
         * @return
         */
        public int m;
        public int n;
        public boolean[][] visit;

        public int numIslands(char[][] grid) {
            //初始化
            m = grid.length;
            n = grid[0].length;
            visit=new boolean[m][n];
            int ans = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == '1' && !visit[i][j]) {
                        dfs(grid, i, j);
                        ans++;
                    }
                }
            }

            return ans;
        }

        public void dfs(char[][] grid, int x, int y) {
            //方向数组
            int[] dx = {-1, 0, 0, 1};
            int[] dy = {0, -1, 1, 0};
            //先标价已访问
            visit[x][y] = true;
            //遍历出边
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                //访问数组前判断合法性
                if (nx < 0 || ny < 0 || nx >= m || ny >= n) {
                    continue;
                }
                if (grid[nx][ny] == '1' && !visit[nx][ny]) {
                    dfs(grid, nx, ny);
                }

            }
        }

//        public void bfs(char[][] grid, int sx, int sy) {
//            //方向数组
//            int[] dx = {-1, 0, 0, 1};
//            int[] dy = {0, -1, 1, 0};
//            Queue<Pair<Integer,Integer>> queue=new ArrayDeque<>();
//            queue.offer(new Pair<>(sx,sy));
//            //入队后标记为已访问
//            visit[sx][sy] = true;
//            while (!queue.isEmpty()){
//                int x=queue.peek().getKey();
//                int y=queue.poll().getValue();
//                //遍历出边
//                for (int i = 0; i < 4; i++) {
//                    int nx = x + dx[i];
//                    int ny = y + dy[i];
//                    //访问数组前判断合法性
//                    if (nx < 0 || ny < 0 || nx >= m || ny >= n) {
//                        continue;
//                    }
//                    if (grid[nx][ny] == '1' && !visit[nx][ny]) {
//                       queue.offer(new Pair<>(nx,ny));
//                       visit[nx][ny]=true;
//                    }
//
//                }
//            }
//        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}